Lexicographical numbers

Time: O(N); Space: O(1); medium

Given an integer n, return 1 - n in lexicographical order.

Example 1:

Input: n = 13

Output: [1,10,11,12,13,2,3,4,5,6,7,8,9].

Notes:

• Please optimize your algorithm to use less time and space.

• The input size may be as large as 5,000,000.

class Solution1(object):
    def lexicalOrder(self, n):
        result = []

        i = 1
        while len(result) < n:
            k = 0
            while i * 10**k <= n:
                result.append(i * 10**k)
                k += 1

            num = result[-1] + 1
            while num <= n and num % 10:
                result.append(num)
                num += 1

            if not num % 10:
                num -= 1
            else:
                num //= 10

            while num % 10 == 9:
                num //= 10

            i = num + 1

        return result

s = Solution1()
n = 13
assert s.lexicalOrder(n) == [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]

See also:

https://leetcode.com/problems/lexicographical-numbers

https://www.lintcode.com/problem/lexicographical-numbers